A social graph is a social structure comprising nodes that connect together via edges or ties to show some sort of interdependency or relationship between the nodes. For instance, the nodes may represent people, organizations, or other sorts of entities. The edges between the nodes may represent interdependency or a relationship between the nodes, such as friends, co-workers, values, visions, dislikes, and/or the like. In one context, nodes of a social graph represent users of a social networking site. The edges, meanwhile, connect those users that have chosen to be within one another's network (i.e., connects users that are “friends”).
In some instances, the larger a social graph becomes, the more useful the social graph becomes to users. As the users of the social graph become increasingly reliant on the graph, the graph may likewise become more valuable to the owner or possessor of the graph (e.g., the social networking site). It is possible, however, for a social graph to continue to grow to a point where the number of users and edge connections dilute the value of the graph itself. Here, the sheer breadth of the social graph makes it difficult for the graph owner or another entity to fully understand the relationships between the users of the social graph.